package com.xigua._递归;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
 * 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
 * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 *给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 * @date 2022/2/2812:12
 */
public class _213_打家劫舍II {

    public static void main(String[] args) {
        System.out.println(rob(new int[]{1,2,3,1}));
    }

    public static int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        int nums1[] = new int[nums.length-1];
        System.arraycopy(nums,0,nums1,0,nums.length-1);
        int nums2[] = new int[nums.length-1];
        System.arraycopy(nums,1,nums2,0,nums.length-1);
        int num1 = rob1(nums1);
        int num2 = rob1(nums2);
        return Math.max(num1,num2);
    }

    public static int rob1(int[] nums) {
        int dp[] =  new int[100];
        dp[0] = nums[0];
        for (int j = 1; j < nums.length; j++) {
            if (j == 1){
                dp[1] = Math.max(nums[0],nums[1]);
            }else {
                dp[j] = Math.max(dp[j-1],dp[j-2]+nums[j]);
            }
        }
        return dp[nums.length-1];
    }

}
